package day_2022_4_to_7.nowcoder;

/**
 * 旋转最小数组
 * @author haomin
 * @date 2022/04/11 10:46
 **/
public class RotateMinArray_5f {
    public static void main(String[] args) {
        int[] array = {2,2,2,1,2};
        System.out.println(minNumberInRotateArray2(array));
    }

    public int minNumberInRotateArray1(int [] array) {
        if(array == null || array.length == 0){
            return 0;
        }
        for(int i = 0; i < array.length-1; i++){
            if(array[i] > array[i+1]){
                return array[i+1];
            }
        }
        return array[0];

    }
    public static int minNumberInRotateArray2(int [] array) {
        // 判空
        if (array == null || array.length == 0) {
            return 0;
        }

        int left = 0;
        int right = array.length - 1;
        int mid = 0;
        while(array[left] >= array[right]){
            if (right - left == 1) {
                mid = right;
                break;
            }

            mid = left + ((right - left) >> 1);
            // 恰巧left right mid 值相等
            if (array[left] == array[mid] && array[left] == array[right]) {
                int restlt = array[left];
                for (int i = left + 1; i < right; i++) {
                    if (restlt > array[i]) {
                        restlt = array[i];
                    }
                }
                return restlt;
            }

            if (array[left] <= array[mid]) {
                // 旋转数在右侧，[mid...right]
                left = mid;
            } else {
                // 旋转数在左侧，[left...mid]
                right = mid;
            }
        }
        return array[mid];
    }
}